//用链表实现栈

//最嚣张
public class MinStack {

    static class ListNode {
        int val;
        ListNode next = null;
        ListNode prev = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    ListNode top = null;
    ListNode MinTop = null;
    public MinStack() {

    }

    public void push(int val) {
        ListNode tmp = new ListNode(val);
        if (top == null) {
            top = tmp;
        } else {
            top.next = tmp;
            tmp.prev = top;
            top = top.next;
        }
        if ((MinTop == null) || (val <= MinTop.val)) {
            ListNode tmp1 = new ListNode(val);
            if (MinTop == null) {
                MinTop = tmp1;
            }else{
                MinTop.next = tmp;
                tmp.prev = top;
                top = top.next;
            }
        }
    }

    public void pop() {
        if (top.val == MinTop.val) {
            MinTop = MinTop.prev;
        }
        top = top.prev;
    }

    public int top() {
        return top.val;
    }

    public int getMin() {
        return MinTop.val;
    }
}

class Stack<E> {
    static class ListNode<E> {
        Object val;
        ListNode next = null;
        ListNode prev = null;

        public ListNode(E val) {
            this.val = val;
        }
    }

    ListNode top = null;

    //尾插
    public void push(E val) {
        ListNode tmp = new ListNode(val);
        if (top == null) {
            top = tmp;
        } else {
            top.next = tmp;
            tmp.prev = top;
            top = top.next;
        }
    }

    //尾删
    public E pop() {
        if (top != null) {
            E ed = (E)top.val;
            top = top.prev;
            return ed;
        }
        return (E)null;
    }

    public E peek() {
        if (top != null) {
            return (E)top.val;
        }
        return (E)null;
    }

    public boolean isEmpty() {
        return top == null;
    }
}


class REXT {
    public static boolean IsPopOrder(int[] pushV, int[] popV) {
        Stack<Integer> pushv = new Stack<>();
        int i = 0;
        for (int x : pushV) {//压入
            pushv.push(x);
            while(i < popV.length && !pushv.isEmpty()&&pushv.peek() == popV[i]) {
                pushv.pop();
                i++;
            }
        }
//        while(i< popV.length && pushv.peek() == popV[i]) {
//            pushv.pop();
//            i++;
//        }
        if (pushv.isEmpty()) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {5,4,3,2,1};
        System.out.println(IsPopOrder(a, b));
    }
    public static void mmain(String[] args) {
        String[] h = {"2","1","+","3","*"};
        String[] hh = {"4","13","5","/","+"};
        System.out.println(evalRPN(hh));
    }
    //计算其原理
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while (i < tokens.length) {

                if (tokens[i].compareTo("+") == 0) {
                    stack.push(stack.pop()+stack.pop());
                } else if (tokens[i].compareTo("-") == 0) {
                    stack.push(-stack.pop()+stack.pop());
                } else if (tokens[i].compareTo("*") == 0) {
                    stack.push(stack.pop()*stack.pop());
                } else if (tokens[i].compareTo("/") == 0) {
                    int prev = stack.pop();
                    int last = stack.pop();
                    stack.push(last / prev);
                } else {
                    stack.push(Integer.parseInt(tokens[i]));
                }
            i++;
        }
        return stack.peek();
    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            } else {//是又括号
                if (stack.isEmpty()) {
                    return false;
                }
                if (stack.peek() == '(' && s.charAt(i) == ')' || stack.peek() == '[' && s.charAt(i) == ']' || stack.peek() == '{' && s.charAt(i) == '}') {
                    stack.pop();
                } else {
                    return false;
                }
            }
            i++;
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    public static void maina(String[] args) {
//        String s = "(({[[]]}))}}}}]";
        String s = "()";
//        System.out.println(isValid(s));

        String ss = "1111";
        System.out.println(String.valueOf(ss) + 1);
        System.out.println(Integer.parseInt(ss) + 1);
    }

    public static void mainm(String[] args) {
        Stack<Character> tmp = new Stack<>();
        tmp.push('w');
        tmp.push('w');
        tmp.push('w');

        System.out.println(tmp.peek());
    }
}

class ttt{
    public static void main1(String[] args) {
        Stack<Character> tmp = new Stack<>();
        tmp.push('w');
        tmp.push('w');
        tmp.push('w');
        tmp.push('q');
        System.out.println(tmp.peek());
        tmp.pop();
        tmp.pop();
        tmp.pop();
        tmp.pop();
        System.out.println(tmp.peek());
    }
}












